package 力扣.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

import static 力扣.堆.堆排序.swap;

public class 全排列II_47 {
    public List<List<Integer>> permuteUnique(int[] nums) {
         if (nums == null){
             return new ArrayList<>();
         }
         List<List<Integer>> ans = new ArrayList<>();
         List<Integer> box = new ArrayList<>();
         backTrace(nums,0,ans,box);
         return ans;
    }

    private void backTrace(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
        final int N = nums.length;
        if (i == N){
            ans.add(new ArrayList<>(box));
        }
        if (i >= N){
            return;
        }
        //记得去重
        HashSet<Integer> hashSet = new HashSet<>();
        for (int j = i; j < N; j++) {
//            if (j > i && nums[j] == nums[i]){
//                continue;
//            }
            if (!hashSet.contains(nums[j])){
                int t = nums[j];
                box.add(t);
                swap(nums,i,j);
                backTrace(nums, i+1, ans, box);
                swap(nums, i, j);
                box.remove(box.size() - 1);
                hashSet.add(t);
            }

        }
    }


    public List<List<Integer>> permuteUnique2(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<>();
        }
//        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        backTrace2(nums,0,ans,box);
        return ans;
    }

    private void backTrace2(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
        final int N = nums.length;
        if (i == N){
            ans.add(new ArrayList<>(box));
        }
        if (i >= N){
            return;
        }
        //记得去重
        HashSet<Integer> set = new HashSet<>();
        for (int j = i; j < N; j++) {
            if (!set.contains(nums[j])){
                //交换代码没写

                box.add(nums[j]);
                backTrace2(nums,  i + 1, ans, box);
                box.remove(box.size() - 1);
                set.add(nums[j]);
            }
        }
    }
}
